package BackTrack.万诺;

import org.junit.Test;
import static MyUtils.MHUtils.*;

/*
无vis0只vis1 也正常回溯
 */
public class 岛屿的最大面积695 {
    @Test
    public void test() {
        int[][] p = {
            {0,0,1,0,0,0,0,1,0,0,0,0,0},
            {0,0,0,0,0,0,0,1,1,1,0,0,0},
            {0,1,1,0,1,0,0,0,0,0,0,0,0},
            {0,1,0,0,1,1,0,0,1,0,1,0,0},
            {0,1,0,0,1,1,0,0,1,1,1,0,0},
            {0,0,0,0,0,0,0,0,0,0,1,0,0},
            {0,0,0,0,0,0,0,1,1,1,0,0,0},
            {0,0,0,0,0,0,0,1,1,0,0,0,0}
        };
        System.out.println(maxAreaOfIsland(p));
    }

    int[][] g;
    int[][] vis;
    int n,m;

    int resMaxS = 0;
    public int maxAreaOfIsland(int[][] grid) {
        g=grid;
        n=g.length; m=g[0].length;
        vis = new int[g.length][g[0].length];

        for (int i = 0; i < g.length; i++) {
            for (int j = 0; j < g[0].length; j++) {
                if(g[i][j] == 1){
                    int x=i,y=j;
                    pre(x,y);
                    quanjuS = 0;
                }
            }
        }
        return resMaxS;
    }

    int[][] fx = {
        {-1,0},
        {1,0},
        {0,-1},
        {0,1}
    };

    int quanjuS = 0;

    private void pre(int i, int j) {

        quanjuS++;
        resMaxS = Math.max(quanjuS, resMaxS);
        vis[i][j] = 1;

        for (int k = 0; k < fx.length; k++) {
            int x = i+fx[k][0], y = j+fx[k][1];
            if(x<0 || x>=n || y<0 || y>=m || g[x][y]==0 || vis[x][y]==1) {
                continue;
            }
            pre(x, y);
        }
    }
}
